Many computers have been designed to execute instructions which are independent of other instructions in a parallel rather than a serial fashion. The decision regarding whether an instruction is independent and a candidate for parallel execution can be made by a computer compiler when source code is compiled, and is a type of compiler optimization.
Another type of compiler optimization comprises data dependence analysis and the determination of computer memory location candidates for redundant load instruction elimination. Re-loading information from memory into a computer register which has previously been loaded by a compiled program is considered a redundant load instruction which wastes computer resources. When the target of a load instruction is the same as a previous store or load instruction, a compiler will attempt to eliminate this redundant load instruction to yield more efficient code. However, determining whether two load instructions access the same memory location is a complicated process.
Dependence analysis is a compiler technology used to determine whether two memory references in a loop access the same memory location, even across loop iterations. That is, dependence analysis is used to determine whether a subsequent register load action will access the same location that was stored on a previous loop iteration. The data dependence phase of compiler optimization also allows independent memory operations to be scheduled concurrently by methods such as pipeline scheduling to exploit instruction level parallelism, while exactly dependent or possibly dependent memory references must continue to be executed in instruction order. The data dependence analysis phase is sometimes termed memory disambiguation. The process of data dependence testing often requires extensive analysis of pairs of memory references in a loop, and is a very large and computer resource intensive solution to apply to the problem of memory disambiguation.
Loop unrolling may be produced by a method of replicating a loop during the process of compilation. Data dependence distance is related to the number of loop iterations and is always an integer value. More particularly, data dependence distance for a dependent memory reference pair is the number of loop iterations required for a second memory reference to reach the same memory reference location as the first memory reference previously accessed. Loop carried dependence occurs when the data dependence distance is greater than zero and therefore, at least one loop iteration is required to reach the distance between two exactly dependent memory references. One of the results of loop unrolling is the reduction of loop carried data dependence across loop iterations. While compiler optimizers may be optionally enhanced by the use of data dependence analysis with loop unrolling, data dependence analysis on an unrolled loop adds significant computer resource overhead to the compiler optimization process.
It should be evident that the current solution to compiler optimization analysis of repetitive loop instructions to determine if the memory reference is independent requires a great deal of computer resources. The large amount of memory references which result from loop unrolling only exacerbates the general problem related to the optimizer overhead involved in data dependence analysis. Current loop unrolling compiler optimizers can create efficient code but at the same time use significant computer resources to process optimization techniques on an unrolled loop which has become larger than the original loop. The opportunities for optimizing computer code for pipeline scheduling to take full advantage of powerful computer hardware and for reduction of register loads have not been fully realized due to the expense associated with data dependence analysis and loop unrolling.